package com.leetcode.程序员面试金典.medium;

import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

/**
 * @author 覃国强
 * @date 2021-04-08 22:52
 */
public class 面试题_17_08_马戏团人塔 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] height = {65,70,56,75,60,68};
    int[] weight = {100,150,90,190,95,110};
    int result = solution.bestSeqAtIndex(height, weight);
    System.out.println(result);
  }


  static
  class Solution {
    public int bestSeqAtIndex(int[] height, int[] weight) {

      Set<Person> set = new TreeSet<>();
      for (int i = 0; i < height.length; ++i) {
        set.add(new Person(height[i], weight[i]));
      }

      int[] ends = new int[set.size()];
      int index = 0;
      int right = 0;
      int maxLength = 1;
      for (Person person : set) {
        if (index == 0) {
          ends[index] = person.weight;
        } else {
          int maxIndex = getLeftMaxWightIndex(person.weight, right, ends);
          ends[maxIndex] = person.weight;
          right = Math.max(right, maxIndex);
          maxLength = Math.max(maxLength, maxIndex + 1);
        }
        ++index;
      }
      return maxLength;
    }

    private int getLeftMaxWightIndex(int weight, int right, int[] ends) {
      int left = 0;
      while (left <= right) {
        int middle = (left + right) / 2;
        if (ends[middle] >= weight) {
          right = middle - 1;
        } else {
          left = middle + 1;
        }
      }
      return left;
    }


    static class Person implements Comparable<Person> {

      int height;

      int weight;

      public Person(int height, int weight) {
        this.height = height;
        this.weight = weight;
      }

      @Override
      public boolean equals(Object o) {
        if (this == o) {
          return true;
        }
        if (o == null || getClass() != o.getClass()) {
          return false;
        }
        Person person = (Person) o;
        return height == person.height && weight == person.weight;
      }

      @Override
      public int hashCode() {
        return Objects.hash(height, weight);
      }

      @Override
      public int compareTo(Person o) {
        int result = this.height - o.height;
        if (result == 0) {
          return o.weight - this.weight;
        }
        return result;
      }
    }
  }

}
